from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:

        n = len(triangle)

        # @cache
        # def dfs(i,j):

        #     # 当到达三角形的下边界时，返回0
        #     if i == n:
        #         return 0  # 不在这里 返回triangle[i][j]，是因为，不知道当前这种情况（i,j），是从哪一种走法来，会出现下标越界
        #     # 递归计算从当前位置到底部的最小路径和，并加上当前位置的值
        #     # 两种 走法
        #     return min(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j]  # 在当前位置进行相加

        # return dfs(0,0)

        # 动态规划
        f = [[0] * (i + 1) for i in range(n)]
        # 讲f的最后一行初始化为三角形的最后一行
        # 因为从最后一行的每个位置到底部的最小路径和就是该位置的值本身
        f[-1] = triangle[-1]
        # 从倒是第二行开始向上遍历三角形的每一行
        for i in range(n - 2, -1, -1):
            # 遍历当前行的每个元素及其索引
            for j, x in enumerate(triangle[i]):
                f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + x
        return f[0][0]